﻿// 算法设计与分析.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <map>


using namespace std;


struct Node {
	char name[10];
	int color;
} v[13];



// 0  1  2  3  4  5  6  7  8  9  10 11 12 
int e[13][13] = { {0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0},	//0
					{0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0},	//1
					{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0},	//2
					{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},	//3
					{1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0},	//4
					{1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0},	//5
					{1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0},	//6
					{0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0},	//7
					{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},	//8
					{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},	//9
					{0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},	//10
					{0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0},	//11
					{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}		//12
};

int main()
{
	int i, j, cnt_color = 1;
	int ct = 0;
	for (i = 0; i < 13; i++)
	{
		int flag = 1;
		if (v[i].color == 0)
		{
			v[i].color = cnt_color;
			printf("第%d种颜色：%5s", cnt_color, v[i].name);
			for (j = 1; j < 13; j++)
			{
				//不相邻且没有着色节点j
				if (e[i][j] == 0 && v[j].color == 0)
				{
					for (int h = 0; h < 13; h++)
					{
						//考察与j相邻的顶点的颜色
						if (e[j][h] == 1 && v[h].color == cnt_color)
						{
							//若有，则j不能着色
							flag = 0;
						}
						ct++;
					}

					//没有相邻且涂同一种颜色的节点，可以给j着色
					if (flag == 1)
					{
						v[j].color = cnt_color;
						printf("%s", v[j].name);
					}
				}
			}
			//用同一种颜色都有能涂完，贪心
			cnt_color++;
			printf("\n");
		}
	}
	printf("总共%d种颜色\n", cnt_color - 1);
	return 0;
}




// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
